#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
using namespace std;
//class Solution {
//public:
//    bool IsTree(TreeNode* root, TreeNode* x)
//    {
//        if (root == nullptr)
//        {
//            return false;
//        }
//        return root == x || IsTree(root->left, x) || IsTree(root->right, x);
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        bool Leftp, Rightp, Leftq, Rightq;
//        Leftp = IsTree(root->left, p);
//        Rightp = !Leftp;
//        Leftq = IsTree(root->left, q);
//        Rightq = !Leftq;
//        if (p == root || q == root)
//        {
//            return root;
//        }
//        if ((Leftp && Rightq) || (Rightp && Leftq))
//        {
//            return root;
//        }
//        else if (Leftp && Leftq)
//        {
//            return lowestCommonAncestor(root->left, p, q);
//        }
//        else {
//            return lowestCommonAncestor(root->right, p, q);
//        }
//    }
//};
bool Getpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{
	if (root == nullptr)
	{
		return false;
	}
	path.push(root);
	if (root == x)
	{
		return true;
	}
	if (Getpath(root->left, x, path))
		return true;;
	
	if (Getpath(root->right, x, path))
		return true;
	if (root != x)
	{
		path.pop();
	}
	return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
	stack<TreeNode*> ppath;
	stack<TreeNode*>qpath;
	Getpath(root, p, ppath);
	Getpath(root, q, qpath);
	while (ppath.size() != qpath.size())
	{
		if (ppath.size() > qpath.size())
			ppath.pop();
		else
			qpath.pop();
	}
	while (ppath.tpo != qpath.tpo())
	{
		ppath.pop();
		qpath.pop();
	}
	return ppath.top();
}